{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Graph Optimization Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Graph "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A <b>graph</b> is a set of objects called <b>nodes(节点) (or vertices(顶)</b> connected by a set of <b>edges（边) (or arcs(弧))</b>.\n",
    "\n",
    "If the edges are <b>unidirectional(单向的）</b> the graph is called <b>a directed graph or digraph</b>.\n",
    "\n",
    "In <b>a directed graph</b>, if there is an edge from $n1$ to $n2$, we refer to $n1$ as the <b>source or parent node</b> and $n2$ as <b>the destination or child node</b>.\n",
    "\n",
    "![](./img/ds/unanddirgraph.jpg)\n",
    "\n",
    "A graph is **complete** if there is an edge from each vertex to every other vertex. the Figure  shows the complete graph\n",
    "\n",
    "\n",
    "![](./img/ds/compgraph.jpg)\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Representations of Graphs\n",
    "\n",
    "To represent graphs, you need a convenient way to store the vertices and the edges that connect them.\n",
    "\n",
    "The two commonly used representations of graphs are the **adjacency matrix(邻接矩阵)** and the **adjacency list(邻接表)**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2.1 Adjacency Matrix\n",
    "\n",
    "The adjacency matrix representation stores the information about a graph in a matrix or grid。 \n",
    "\n",
    "Recall that a matrix has two dimensions, and each cell is accessed at a given row and column position. \n",
    "\n",
    "Assume that a graph has $N$ vertices labeled $0, 1, . . ., N – 1$, and then the following applies:\n",
    "\n",
    "* The adjacency matrix for the graph is a grid $G$ with $N$ rows and $N$ columns.\n",
    "\n",
    "* The cell $G[i][j]$ contains $1$ if there is an edge from vertex $i$ to vertex $j$ in the graph. Otherwise,there is no edge, and that cell contains $0$.\n",
    "\n",
    "The Figure shows a directed graph and its adjacency matrix. Each node in the graph is labeled with a letter. Next to each node is its row number in the adjacency matrix.\n",
    "\n",
    "![dirgraph-am](./img/ds/dirgraph-am.jpg)\n",
    "\n",
    "If the graph is **undirected**, then `four more` cells are occupied by $1$ to account for the **bidirectional** character of each edge. see the Figure.\n",
    "\n",
    "\n",
    "![undirgraph-am](./img/ds/undirgraph-am.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2.2 Adjacency List\n",
    "\n",
    "The follow Figure shows a directed graph and its adjacency list representation.\n",
    "\n",
    "An adjacency list representation stores the information about a graph in an array of lists. \n",
    "\n",
    "You can use either linked or array-based list implementations. \n",
    "\n",
    "This example uses a linked list implementation.\n",
    "\n",
    "Assume that a graph has $N$ vertices labeled $0, 1, . . ., N – 1$, and then the following applies:\n",
    "\n",
    "* The adjacency list for the graph is an array of $N$ linked lists.\n",
    "\n",
    "* The $i$th linked list contains a node for vertex $j$ if and only if there is an edge from vertex $i$ to vertex $j$.\n",
    "\n",
    "![dirgraph-al](./img/ds/dirgraph-al.jpg)\n",
    "\n",
    "Note that the labels of the vertices are included in the nodes for each edge. Naturally, there would be twice as many nodes in an undirected graph,see the Figure.\n",
    "\n",
    "![undirgraph-al](./img/ds/undirgraph-al.jpg)\n",
    "\n",
    "When the edges have weights, the weights can also be included as a second data field in the nodes, as shown in the Figure\n",
    "\n",
    "![dirgraph-alw](./img/ds/dirgraph-alw.jpg)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.2.3 Analysis of the Two Representations\n",
    "\n",
    "As far as running time is concerned, the behavior of two commonly used graph operations illustrates the difference in `computational efficiency` between the adjacency matrix and the adjacency list. \n",
    "\n",
    "##### Operations\n",
    "These operations are the following:\n",
    "\n",
    "* Determine whether or not there is an **edge** between two given vertices.\n",
    "\n",
    "* Find `all the vertices adjacent` to a given vertex\n",
    "\n",
    "**Determine whether or not there is an `edge` between two given vertices**\n",
    "\n",
    "* The `adjacency matrix` supports the first operation in **constant time** because it requires just an **index** operation into a two-dimensional array. \n",
    "\n",
    "* The linked `adjacency list` requires an index into `an array of linked lists` and then a search of a linked list for a target vertex. \n",
    "\n",
    "  * The running time is `linear with the length of this list`$O(N)$, on the average. \n",
    "\n",
    "**Find all the vertices adjacent  to a given vertex**\n",
    "\n",
    "The `adjacency list` tends to support finding all the vertices adjacent to a given vertex `more efficiently` than the adjacency matrix.\n",
    "\n",
    "* In the adjacency list, the set of adjacent vertices for a given vertex is simply the list for that vertex, which can be located with one **index** operation.\n",
    "\n",
    "The set of adjacent vertices for a given vertex in the `adjacency  matrix` must be computed by traversing that vertex’s row in the matrix and accumulating just those positions that contain $1$. \n",
    "\n",
    "The operation must always visit $N$ cells in the adjacency matrix, whereas the operation typically visits much fewer than $N$ nodes in an adjacency list. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Memory\n",
    "As far as memory usage is concerned, \n",
    "\n",
    "the `adjacency matrix` always requires $N^2$ cells, no matter how many edges connect the vertices. Thus, the only case in which no cells are wasted is that of a complete graph.\n",
    "\n",
    "the `adjacency list` requires an array of $N$ pointers and a number of nodes equal to twice the number of edges in the case of an undirected graph. The number of edges typically is much smaller than $N^2$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Comparison\n",
    "\n",
    "$V$: numbers of  vertexs\n",
    "\n",
    "$E$: numbers of edges\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](./img/ds/graph-comp.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.3 The Graph Class \n",
    "\n",
    "#### 2.3.1 The class :Node\n",
    "\n",
    "The follow code contains classes implementing abstract types corresponding to nodes, weighted edges, and edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, name):\n",
    "        \"\"\"Assumes name is a string\"\"\"\n",
    "        self._name = name\n",
    "    def get_name(self):\n",
    "        return self._name\n",
    "    def __str__(self):\n",
    "        return self._name\n",
    "\n",
    "class Edge:\n",
    "    def __init__(self, src, dest):\n",
    "        \"\"\"Assumes src and dest are nodes\"\"\"\n",
    "        self._src = src\n",
    "        self._dest = dest\n",
    "    def get_source(self):\n",
    "        return self._src\n",
    "    def get_destination(self):\n",
    "        return self._dest\n",
    "    def __str__(self):\n",
    "        return self._src.get_name() + '->' + self._dest.get_name()\n",
    "\n",
    "class Weighted_edge(Edge):\n",
    "    def __init__(self, src, dest, weight = 1.0):\n",
    "        \"\"\"Assumes src and dest are nodes, weight a number\"\"\"\n",
    "        super().__init__(self, src, dest)\n",
    "        self._weight = weight\n",
    "    \n",
    "    def get_weight(self):\n",
    "        return self._weight\n",
    "    \n",
    "    def __str__(self):\n",
    "        return (f'{self._src.get_name()}->({self._weight})' +\n",
    "               f'{self._dest.get_name()}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "####  2.3.2 The classes `Digraph` and `Graph`\n",
    "\n",
    "The codes contains implementations of the classes\n",
    "\n",
    "* <b>Digraph</b> \n",
    "\n",
    "* <b>Graph</b>\n",
    "\n",
    "In the code，we use <b style=\"color:blue\">the adjacency list</b> representation. \n",
    "\n",
    "Class <b>Digraph</b> has two instance variables:\n",
    "\n",
    "* <b>nodes</b> is a Python list containing the names of the nodes in the Digraph. The connectivity of the nodes is represented using an adjacency list implemented as a `dictionary`.\n",
    "\n",
    "* <b>edges</b> is `a dictionary` that maps each Node in the Digraph to a **list** of the children of that Node: **the adjacency list**\n",
    "```python\n",
    " self.edges[src].append(dest)\n",
    "```\n",
    "\n",
    "![](./img/ds/17.9.PNG) \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The adjacency list representation:**\n",
    "\n",
    "```python\n",
    "{ 0: [1, 2], \n",
    "  1: [2，0],\n",
    "  2: [3,4],\n",
    "  3: [4,5,1],\n",
    "  4: [0],\n",
    "  5:[]\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Class **Graph** is a subclass of `Digraph`. It inherits all of the methods of Digraph except `addEdge`, which it overrides.\n",
    "\n",
    "* The Class `Graph` stores each edge **twice**, once for each direction in the Digraph. This is not the most space-efficient way to implement Graph,but it has the virtue of simplicity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Digraph:\n",
    "    # nodes is a list of the nodes in the graph\n",
    "    # edges is a dict mapping each node to a list of its children\n",
    "    def __init__(self):\n",
    "        self._nodes = []\n",
    "        self._edges = {}\n",
    "        \n",
    "    def add_node(self, node):\n",
    "        if node in self._nodes:\n",
    "            raise ValueError('Duplicate node')\n",
    "        else:\n",
    "            self._nodes.append(node)\n",
    "            self._edges[node] = []\n",
    "    \n",
    "    def add_edge(self, edge):\n",
    "        src = edge.get_source()\n",
    "        dest = edge.get_destination()\n",
    "        if not (src in self._nodes and dest in self._nodes):\n",
    "            raise ValueError('Node not in graph')\n",
    "        self._edges[src].append(dest)\n",
    "    \n",
    "    def children_of(self, node):\n",
    "        return self._edges[node]\n",
    "    \n",
    "    def has_node(self, node):\n",
    "        return node in self._nodes\n",
    "    \n",
    "    def __str__(self):\n",
    "        result = ''\n",
    "        for src in self._nodes:\n",
    "            for dest in self._edges[src]:\n",
    "                result = (result + src.get_name() + '-> '\n",
    "                         + dest.get_name() + '\\n')\n",
    "        return result[:-1] #omit final newline\n",
    "    \n",
    "    def display(self): \n",
    "        result=\"Node -> Adjacency List:\\n\" \n",
    "        for src in self._nodes:\n",
    "            result +=\"Node {:2s}->[\".format(src.get_name())\n",
    "            for dest in self._edges[src]:\n",
    "                 result +=\"{:2s} \".format(dest.get_name())\n",
    "            result +=\"]\\n\"\n",
    "        return result \n",
    "\n",
    "class Graph(Digraph):\n",
    "    \n",
    "    def add_edge(self, edge):\n",
    "        super().add_edge(self, edge)\n",
    "        rev = Edge(edge.get_destination(), edge.get_source())\n",
    "        super().add_edge(self, rev)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Node -> Adjacency List:\n",
      "0 ->[1  2  ]\n",
      "1 ->[0  2  ]\n",
      "2 ->[3  4  ]\n",
      "3 ->[4  5  1  ]\n",
      "4 ->[0  ]\n",
      "5 ->[]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "nodes = []\n",
    "for name in range(6): #Create 6 nodes\n",
    "    nodes.append(Node(str(name)))\n",
    "g = Digraph()\n",
    "for n in nodes:\n",
    "    g.add_node(n)\n",
    "\n",
    "g.add_edge(Edge(nodes[0],nodes[1]))\n",
    "g.add_edge(Edge(nodes[0],nodes[2]))\n",
    "\n",
    "g.add_edge(Edge(nodes[1],nodes[0]))\n",
    "g.add_edge(Edge(nodes[1],nodes[2]))\n",
    "\n",
    "g.add_edge(Edge(nodes[2],nodes[3]))\n",
    "g.add_edge(Edge(nodes[2],nodes[4]))\n",
    "\n",
    "g.add_edge(Edge(nodes[3],nodes[4]))\n",
    "g.add_edge(Edge(nodes[3],nodes[5]))\n",
    "g.add_edge(Edge(nodes[3],nodes[1]))\n",
    "g.add_edge(Edge(nodes[4],nodes[0]))\n",
    "print(g.display())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 Some Classic Graph-Theoretic Problems\n",
    "\n",
    "Some of the best-known graph optimization problems are:\n",
    "\n",
    "* <b>Shortest path</b>. For some pair of nodes, $𝑛1$ and $𝑛2$, find the shortest sequence of edges $<S_𝑛, D_𝑛>$ (source node and destination node), such that\n",
    "\n",
    "  * The source node in the first edge is $n1$\n",
    "  * The destination node of the last edge is $n2$\n",
    "  * For all edges $e1$ and $e2$ in the sequence, if $e2$ follows $e1$ in the sequence, the source node of $e2$ is the destination node of $e1$.\n",
    "\n",
    "\n",
    "* <b>Shortest weighted path</b>. This is like the shortest path, except instead of choos-ing the shortest sequence of edges that connects two nodes, we define some function on the weights of the edges in the sequence (e.g., their sum) and min-imize that value. This is the kind of problem solved by Google and Apple Maps when asked to compute driving directions between two points.\n",
    "\n",
    "    \n",
    "* <b>Min cut</b>. Given two sets of nodes in a graph, a <b>cut</b> is a set of edges whose removal <b>eliminates all paths</b> from each node in one set to each node in the other.The minimum cut is the smallest set of edges whose removal accomplishes this.\n",
    "\n",
    "\n",
    "* <b>Maximum clique</b>. A clique is a set of nodes such that there is an edge between each pair of nodes in the set. A maximum clique is a clique of the largest size in a graph. The minimum cut is the smallest set of edges whose removal ac-complishes this. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "\n",
    "### 2.5 The Shortest Path\n",
    "\n",
    "It is often useful to determine **the shortest path** between two vertices in a graph. Consider an airline map, represented as a weighted directed graph whose weights represent miles between airports.\n",
    "\n",
    "The shortest path between two airports is the path that has the smallest sum of edge weights.\n",
    "\n",
    "The **single-source shortest-path problem** asks for a solution that contains the shortest paths from a given vertex to all the other vertices.\n",
    "\n",
    "\n",
    "#### 2.5.1 Depth-first search (DFS)\n",
    " \n",
    "The algorithm implemented by DFS is an example of a recursive <b>depth-first search (DFS)深度优先搜索 </b> algorithm.\n",
    "\n",
    "In general, a depth-first-search algorithm begins by choosing one child of the start node. It then chooses one child of that node and so on, going deeper and deeper until it either reaches the goal node or a node with no children. \n",
    "\n",
    "The search then <b>backtracks</b>, returning to <b>the most recent node with children that it has not yet visited</b>. \n",
    "\n",
    "\n",
    "* 深度优先搜索首先选择一个节点作为起始节点，然后，选择这个节点的一个子节点，继续这个过程，越走越深，直到到达目标节点或者没有子节点的节点，之后，开始回溯，退回到子节点没有被访问的最近节点\n",
    "\n",
    "<img src=\"./img/ds/dfs.jpg\"/> \n",
    "\n",
    "When all paths have been explored, it chooses the shortest path (assuming that there is one) from the start\n",
    "to the goal.\n",
    "\n",
    "The follow code is a bit more complicated than the algorithm we just described：\n",
    "\n",
    "1. It has to deal with the possibility of the graph containing **cycles**.\n",
    "\n",
    "2. It also avoids exploring paths longer than the shortest path that it has already found\n",
    "\n",
    "In the follow code DFS \n",
    "\n",
    "* The function `shortest_path` calls `DFS` with `path = []` (to indicate that the current path being explored is empty) and `shortest = None` (to indicate that no path from start to end has yet been found).\n",
    "\n",
    "*  DFS begins by choosing one child of `start`. It then chooses one child of that node and so on, until either it reaches the node end or a node with no unvisited children.\n",
    "  \n",
    "  * The check ```if node not in path``` prevents the program from getting caught in a cycle.\n",
    "\n",
    "  * The check ```if shortest == None or len(path) < len(shortest)``` is used to decide if it is possible that continuing to search this path might yield a shorter path than the best path found so far.\n",
    "  * If so, DFS is called recursively. If it finds a path to end that is no longer than the best found so far, `shortest` is updated.\n",
    "\n",
    "  * When the last node on `path` has no children left to visit, the program backtracks to the previously visited node and visits the next child of that node.\n",
    "\n",
    "* The function returns when all possibly shortest paths from start to end have been explored.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_path(path):\n",
    "    \"\"\"Assumes path is a list of nodes\"\"\"\n",
    "    result = ''\n",
    "    for i in range(len(path)):\n",
    "        result = result + str(path[i])\n",
    "        if i != len(path) - 1:\n",
    "            result = result + '->'\n",
    "    return result \n",
    "\n",
    "def DFS(graph, start, end, path, shortest, to_print = False):\n",
    "    \"\"\"Assumes graph is a Digraph; start and end are nodes;\n",
    "          path and shortest are lists of nodes\n",
    "       Returns a shortest path from start to end in graph\"\"\"\n",
    "    path = path + [start]\n",
    "    \n",
    "    if to_print:\n",
    "        print('Current DFS path:', print_path(path))\n",
    "   \n",
    "    if start == end:\n",
    "        return path\n",
    "    for node in graph.children_of(start):\n",
    "        if node not in path: # avoid cycles\n",
    "            if shortest == None or len(path) < len(shortest):\n",
    "                new_path = DFS(graph, node, end, path, shortest,\n",
    "                              to_print)\n",
    "                if new_path != None:\n",
    "                    shortest = new_path\n",
    "    return shortest\n",
    "\n",
    "def shortest_path(graph, start, end, to_print = False):\n",
    "    \"\"\"Assumes graph is a Digraph; start and end are nodes\n",
    "       Returns a shortest path from start to end in graph\"\"\"\n",
    "    return DFS(graph, start, end, [], None, to_print)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `test_SP` first builds a directed graph like the one pictured on the right, and then \n",
    "\n",
    "* searches for a shortest path between **node 0 and node 5**.\n",
    "\n",
    "<img src=\"./img/ds/17.9.PNG\"/> "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_SP():\n",
    "    nodes = []\n",
    "    for name in range(6): #Create 6 nodes\n",
    "        nodes.append(Node(str(name)))\n",
    "    g = Digraph()\n",
    "    for n in nodes:\n",
    "        g.add_node(n)\n",
    "    g.add_edge(Edge(nodes[0],nodes[1]))\n",
    "    g.add_edge(Edge(nodes[1],nodes[2]))\n",
    "    g.add_edge(Edge(nodes[2],nodes[3]))\n",
    "    g.add_edge(Edge(nodes[2],nodes[4]))\n",
    "    g.add_edge(Edge(nodes[3],nodes[4]))\n",
    "    g.add_edge(Edge(nodes[3],nodes[5]))\n",
    "    g.add_edge(Edge(nodes[0],nodes[2]))\n",
    "    g.add_edge(Edge(nodes[1],nodes[0]))\n",
    "    g.add_edge(Edge(nodes[3],nodes[1]))\n",
    "    g.add_edge(Edge(nodes[4],nodes[0]))\n",
    "    # searches for a shortest path between node 0 and node 5.\n",
    "    sp = shortest_path(g, nodes[0], nodes[5], to_print = True)\n",
    "    print('\\nShortest path found by DFS:', print_path(sp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current DFS path: 0\n",
      "Current DFS path: 0->1\n",
      "Current DFS path: 0->1->2\n",
      "Current DFS path: 0->1->2->3\n",
      "Current DFS path: 0->1->2->3->4\n",
      "Current DFS path: 0->1->2->3->5\n",
      "Current DFS path: 0->1->2->4\n",
      "Current DFS path: 0->2\n",
      "Current DFS path: 0->2->3\n",
      "Current DFS path: 0->2->3->4\n",
      "Current DFS path: 0->2->3->5\n",
      "Current DFS path: 0->2->3->1\n",
      "Current DFS path: 0->2->4\n",
      "\n",
      "Shortest path found by DFS: 0->2->3->5\n"
     ]
    }
   ],
   "source": [
    "test_SP()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that after exploring the path `0->1->2->3->4` \n",
    "\n",
    "* it backs up to node 3 and explores the path `0->1->2->3->5` \n",
    "\n",
    "After saving that as the shortest successful path so far, \n",
    "\n",
    "* it backs up to node 2 and explores the path:`0->1->2->4`. \n",
    "\n",
    "When it reaches the end of that path (`node 4`),\n",
    "\n",
    "* it backs up all the way to `node 0` and  investigates the path starting with the `edge from 0 to 2`. And so on."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### 2.5.2 Breadth-first search (BFS). \n",
    "\n",
    "There are other ways to traverse a graph than depth-first. Another common approach is <b>breadth-first search(BFS)广度优先搜索</b>. \n",
    "\n",
    "\n",
    "A breadth-first traversal first visits all children of the start node. If none of those is the end node, it visits all children of each of those nodes. And so on.\n",
    "\n",
    "* 广度优先搜索，首先访问开始节点的所有子节点。如果这些节点都不是结束节点，那么它将访问每个节点的所有子节点\n",
    "\n",
    "![](./img/ds/graphsearch.jpg)\n",
    "\n",
    "Unlike depth-first search, which is usually implemented recursively, breadth-first search is usually implemented <b>iteratively<b>. \n",
    "\n",
    "<b>BFS explores many paths simultaneously<b>, adding one node to each path on each iteration. Since it generates the paths in <b>ascending order of length</b> , <b>the first path found</b>  with the goal as its last node is guaranteed to </b> have a minimum number of edges</b> .\n",
    "\n",
    "\n",
    "\n",
    "The following code that uses a breadth-first search to find the shortest path in a directed graph.\n",
    "\n",
    "The variable <b>pathQueue</b> is used to store all of the paths currently being explored. \n",
    "\n",
    "Each iteration starts by <b>removing a path from pathQueue and assigning that path tmpPath</b>. If the last node in tmpPath is end, tmpPath is returned. Otherwise, a set of new paths is created, each of which extends tmpPath by adding one of its children. Each of these new paths is then added to pathQueue."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BFS(graph, start, end, to_print = False):\n",
    "    \"\"\"Assumes graph is a Digraph; start and end are nodes\n",
    "       Returns a shortest path from start to end in graph\"\"\"\n",
    "    init_path = [start]\n",
    "    path_queue = [init_path]\n",
    "    while len(path_queue) != 0:\n",
    "        #Get and remove oldest element in path_queue\n",
    "        tmp_path = path_queue.pop(0)\n",
    "        if to_print:\n",
    "            print('Current BFS path:', print_path(tmp_path))\n",
    "        last_node = tmp_path[-1]\n",
    "        if last_node == end:\n",
    "            return tmp_path\n",
    "        for next_node in graph.children_of(last_node):\n",
    "            if next_node not in tmp_path:\n",
    "                new_path = tmp_path + [next_node]\n",
    "                path_queue.append(new_path)\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test_sp modifed as per code \n",
    "def test_SP():\n",
    "    nodes = []\n",
    "    for name in range(6): #Create 6 nodes\n",
    "        nodes.append(Node(str(name)))\n",
    "    g = Digraph()\n",
    "    for n in nodes:\n",
    "        g.add_node(n)\n",
    "    g.add_edge(Edge(nodes[0],nodes[1]))\n",
    "    g.add_edge(Edge(nodes[1],nodes[2]))\n",
    "    g.add_edge(Edge(nodes[2],nodes[3]))\n",
    "    g.add_edge(Edge(nodes[2],nodes[4]))\n",
    "    g.add_edge(Edge(nodes[3],nodes[4]))\n",
    "    g.add_edge(Edge(nodes[3],nodes[5]))\n",
    "    g.add_edge(Edge(nodes[0],nodes[2]))\n",
    "    g.add_edge(Edge(nodes[1],nodes[0]))\n",
    "    g.add_edge(Edge(nodes[3],nodes[1]))\n",
    "    g.add_edge(Edge(nodes[4],nodes[0]))\n",
    "    sp = shortest_path(g, nodes[0], nodes[5], to_print = True)\n",
    "    print('\\tShortest path found by DFS:', print_path(sp))\n",
    "    #\n",
    "    print('\\nShortest path by BFS:') \n",
    "    sp = BFS(g, nodes[0], nodes[5], to_print = True)\n",
    "    print('\\tShortest path found by BFS:', print_path(sp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current DFS path: 0\n",
      "Current DFS path: 0->1\n",
      "Current DFS path: 0->1->2\n",
      "Current DFS path: 0->1->2->3\n",
      "Current DFS path: 0->1->2->3->4\n",
      "Current DFS path: 0->1->2->3->5\n",
      "Current DFS path: 0->1->2->4\n",
      "Current DFS path: 0->2\n",
      "Current DFS path: 0->2->3\n",
      "Current DFS path: 0->2->3->4\n",
      "Current DFS path: 0->2->3->5\n",
      "Current DFS path: 0->2->3->1\n",
      "Current DFS path: 0->2->4\n",
      "\tShortest path found by DFS: 0->2->3->5\n",
      "\n",
      "Shortest path by BFS:\n",
      "Current BFS path: 0\n",
      "Current BFS path: 0->1\n",
      "Current BFS path: 0->2\n",
      "Current BFS path: 0->1->2\n",
      "Current BFS path: 0->2->3\n",
      "Current BFS path: 0->2->4\n",
      "Current BFS path: 0->1->2->3\n",
      "Current BFS path: 0->1->2->4\n",
      "Current BFS path: 0->2->3->4\n",
      "Current BFS path: 0->2->3->5\n",
      "\tShortest path found by BFS: 0->2->3->5\n"
     ]
    }
   ],
   "source": [
    "test_SP()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comfortingly, each algorithm found a path of the same length. In this case, they found the same path. However, if a graph contains more than one shortest path between a pair of nodes, DFS and BFS will not necessarily find the same\n",
    "shortest path.\n",
    "\n",
    "BFS is a convenient way to search for a path with the fewest edges because **the first time a path is found, it is guaranteed to be such a path**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Further Reading: NetworkX\n",
    "\n",
    "NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks\n",
    "\n",
    "https://github.com/networkx/networkx\n",
    "\n",
    ">python -m pip install networkx\n",
    "\n",
    "###  Example:NetworkX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 2, 3, 5]\n"
     ]
    }
   ],
   "source": [
    "# DiGraph\n",
    "import networkx as nx\n",
    "G=nx.DiGraph()\n",
    "G.add_nodes_from([0,1,2,3,4,5])\n",
    "G.add_edges_from([(0,1),(1,2),(2,3),(2,4),(3,4),(3,5),(0,2),(1,0),(3,1),(4,0)])  \n",
    "\n",
    "try:\n",
    "    path=nx.shortest_path(G,0,5)\n",
    "    print(path)\n",
    "except nx.NetworkXNoPath:\n",
    "    print('No path')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 2, 3, 5]\n"
     ]
    }
   ],
   "source": [
    "# Graph\n",
    "import networkx as nx\n",
    "G=nx.Graph()\n",
    "G.add_nodes_from([0,1,2,3,4,5])\n",
    "G.add_edges_from([(0,1),(1,2),(2,3),(2,4),(3,4),(3,5),(0,2),(1,0),(3,1),(4,0)])  \n",
    "\n",
    "try:\n",
    "    path=nx.shortest_path(G,0,5)\n",
    "    print(path)\n",
    "except nx.NetworkXNoPath:\n",
    "    print('No path')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "dijkstra_path_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import networkx as nx\n",
    "g = nx.Graph()\n",
    "g.add_edge('a', 'b', distance=0.3)\n",
    "g.add_edge('a', 'c', distance=0.7)\n",
    "nx.dijkstra_path_length(g, 'b', 'c', 'distance')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Drawing graphs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAKYAAADnCAYAAACUjC2+AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Il7ecAAAACXBIWXMAAAsTAAALEwEAmpwYAAA3V0lEQVR4nO2deViUVRfAf8OAICLggrikiGngvmKk4pJLSgrmkhhkWm5pVpZm6pdaamaWbQampWZqiLjivlsuiEuGKSiaGyYgiOwzwMz9/qAhkGGbfYDf8/g8NO997z3QmXvuvefccyRCCEEVVZgYFsYWoIoq1FGlmFWYJFWKWYVJUqWYVZgkVYpZhUlSpZhVmCSWxhbAVElMlxN6IZbouFRSZbnY21jiXt+ekZ2foo6dtbHFq/BIqs4xC/Pnvcd8f/wGJ64/BECeq8x/ZmNpgQB6uzkxpVdz2jd2NI6QlYAqxSzAhvDbLN4bjSxXQUl/FYkEbCylzPV2J8CzqcHkq0xUmfJ/yVPKKLJylKW2FQKychQs3hsFUKWceqBq80Oe+V68N7pMSlmQrBwli/dGExn7WD+CVWKqZkzg++M3kOUq1D7LvHaalDNbyEm8A1JLqjk1xWnEPKQ2dgDIchUEHr/ByoAuhhS5wlPpFTMxXc6J6w/Vrikzrp4gcdcykFph+4wnFlbVkT+4jsiRwb+KKQQcu/aQpHR51W5dh1R6xQy9EKv2cyEEycfXAeD88sfYuLQrtg8JEHoxlkk9n9aDhJWTSq+Y0XGphY6EVOQm/4Mi9SESS2tSzm4lIfQTpDVqYe/hS83Ogwu1leUqiX6QZiiRKwWVfvOTKstV+7kiMxUAkSsn93E8tu49UKQn8ejQSjKvn1HTT45e5axsVHrFtLdRbzSktvb5P9cd8h51X3yXGu36A5AZc1ZNP1b6EbCSUukV072+PdaWRf8Mlg71kFjbqn3Holr1Qv9tY2mBe4OaepGvslLpFXNE56fUfi6RWmHfxReAxN3LSdzzNRmRh0BiQY3WvQu1FcCITur7qUIzKr1i1rWzptczTkgkRZ85dPfD3nMEQpZBZvTvWNV1od6Ij7Bu6JbfRiiV2KbcIi3xgQGlrvhU+crJ8/z4rQ4nK0f9IXtJ2FhZMMDiCptWfMYbb7zBnDlzcHBw0IOUlYtKP2MCtG/siFfNh5ArL9d71a0s+J93S75dMIPIyEgSExNxc3MjMDCQ3Fz1u/0qykaVYgKbNm1i7zezebeXC9WtpGrNekEkEqhuJWWud8v8AI6GDRvy008/ceDAAbZt20bbtm3Zs2cPVQZJMyq9KQ8LC2PChAkcPnyYNm3aEBn7mMDjNzh27SES8g7PVajiMfu4OTGld3PaPeWotk8hBHv37mXGjBk0atSIL7/8kvbt2xvk96kwiErMsWPHhJOTkzh79myRZ4lpMrHyxA3RctwS4fvlPvFu8B9i5YkbIjFNVub+s7Ozxffffy+cnZ3F66+/Lu7fv69L8Ss0lVYxIyIihJOTkzh69GiJ7Tp27CjOnz+v1ViPHz8Ws2bNErVr1xYff/yxSE9P16q/ykClXGNeuXKFIUOG8NNPP9GnT58S22ZkZFCjRg2txnNwcOCzzz7jwoULREVF4ebmxs8//4xSWb74z0qFsb8ZhubmzZuiUaNGYuPGjWVq36hRI3H37l2dynDmzBnx3HPPiY4dO5Y6Y1dWKpVixsbGCldXVxEUFFTmdxwcHMSjR490LotSqRSbN28Wrq6uwsfHR0RHR+t8DHOm0ijmw4cPRatWrcRnn31WrvcsLS2FXC7Xk1RCyGQysWzZMlG3bl0xbdo08fDhQ72NZU5UijVmamoqgwYNwsfHh1mzZpX5vezsbACqVaumL9GwtrZmxowZREVFIYSgZcuWfPHFF8jl5Tvsr3AY+5uhbzIzM0WvXr3E5MmThVKpLNe7SUlJwsHBQT+CFUNUVJQYMmSIaNasmQgJCSm3zBWFCq2Y2dnZ4sUXXxSvvPKKUCgU5X7/7t27olGjRnqQrHSOHDkiOnToILp16ybCw8ONIoMxqbCmXKFQMGbMGCQSCevWrcPCovy/qi6OijTl+eef5/z580yYMIHhw4czevRobt++bRRZjEGFVEwhBFOnTiUuLo6QkBCsrDSLLjemYgJIpVLGjh3LtWvXcHd3p3Pnznz44YekpKQYTSZDUeEUUwjBhx9+yMWLF9m1axfVq1cv/aViSE9Px87OTofSaUaNGjWYP38+ly9fJiEhATc3N4KCgip0BFOFU8zPPvuMPXv2sG/fPmrW1O66g7FnzCdp2LAha9asYf/+/YSGhtKuXTv27t1bISOYKpRiBgYG8uOPP3Lw4EHq1KmjdX+mppgqOnTowOHDh/n88895//33GTBgAJGRkcYWS6dUGMXcsGEDS5Ys4fDhwzRs2FAnfaanp5ukYgJIJBIGDx5MZGQkQ4cOpX///owfP54HDyrGFY8KoZi7du1ixowZHDhwAFdXV531m5GRYRJrzJKwsrJi6tSpXLt2jdq1a9OmTRsWLlxIZmamsUXTCrNXzKNHjzJ+/Hh2795Nq1atdNq3qZpydTg6OvL5559z/vx5rly5gpubG+vXrzfbCCazVsyzZ8/i5+fHli1b6NJF99nWzEkxVbi6uhIcHExISAhBQUF4eHhw/PhxY4tVbsxWMS9fvoyPjw9r166lV69eehnDVI6LNOG5557j9OnTfPDBB4wbN46hQ4dy/fp1Y4tVZsxSMW/cuMHAgQP5+uuvefHFF/U2jjnOmAWRSCSMGjWKqKgounfvTrdu3XjnnXdISkoytmilYnaKGRsbS//+/Zk/fz6jR4/W61jmrpgqbGxsmDlzJlFRUSgUCtzd3fnyyy9NOoLJrBTz4cOH9O/fnylTpjBx4kS9j2fKx0Wa4OTkxIoVK/jtt984fvw4rVq1IjQ01CQP6M1GMVNSUhg4cCDDhg1j5syZBhnTHI6LNKFly5aEhYWxatUqFi1ahJeXFxEREcYWqxBmoZiZmZkMGTIET09PFi1aZLBxK4opL46+ffty4cIF3njjDV566SX8/f25c+eOscUCzEAxs7OzGTFiBC4uLnz33XdISkuToUMqumJCXgTTuHHjuHbtGi1atKBTp07Mnj2b1NRUo8pl0oqpiqm0srJizZo1GsVUaoM5HxeVFzs7OxYsWEBkZCRxcXG4ubmxcuVKo0UwmaxiCiGYPHkyCQkJbN68WeOYSm2oDDPmkzRq1Ii1a9eyd+9eQkJCaN++Pfv27TP4BskkcxcJIZg5cyYnT57k0KFDWoevaUrNmjW5f/8+9vb2pTeugAgh2L17NzNmzMDFxYUvv/yStm3blvqeLgrEmqRiLl68mODgYE6cOEHt2rWNIoMQAqlUSk5ODlKp1CgymAo5OTn88MMPLFy4EB8fHxYuXEj9+vWLtNNlgViTM+UrVqxg7dq1HDx40GhKCZCVlYW1tXWlV0rIi2B66623uHbtGo6OjrRp04ZFixYVimDaEH4bv9XhHIqKR56rLFKiRvbvZwevxuO3OpwN4bdLHNOkFHP9+vUsXbqUw4cP06BBA6PKUhnXl6Xh6OjIsmXLiIiIIDIyEjc3N3755RfWn7n1b4HYkqsWQ+ECsSUpp8mY8h07dvDmm29y9OhRWrZsaWxxuH37Nr169TKZcz1T5PTp00ybv4ykjmNAWjgpRHbiXR4fW4v8n2sIRQ42Lu2p3W8ilg718ttUt5IS9clAtX2bxIx55MgRJk6cyO7du01CKaFyHRVpSrdu3eg8Zi4SaeETE6UsnYTg/5F18xzWDd2o3rQjWTHhJGxZgBD/mfjiCsuCCShmeHg4o0ePJjQ0lM6dOxtbnHyqTHnp5BeIpbDTQxYbhSL9EVIHZ+qNnI/TsDlY1XMlJ/Eumdf+qypXkq02qmJGRkbi6+vLunXr6NmzpzFFKUKVYpZOcQViJZZ5M6gyK5Wcx3HkpiaiSH8EQE7CrTL1bbQipzExMQwaNIhvv/0Wb29vY4lRLBUtskgfFFcg1qZJW6yfaoU89ir/rBxf6JkiI7lMfRtFMe/du0f//v35+OOPGTVqlDFEKJWKGlmkS1Iys9V+LrGQ4jz6UzKifycn8R6W9k7I7v1F5tUTWNiWrQaSwRVTFVM5bdo0xo8fX/oLRqLKlBdGqVRy48YNzp07x7lz54iIiOBvZy9s3ItbggnsWuelEVdkpvD4t18AqN60Q5nGM6hipqSk8MILLzBy5Ejef/99Qw5dbiq7Yt6/f5+IiIh8RTx//jz29vZ4eHjQtWtXFi9eTGR2PQJP3lVrzuODP0Ja3R6JTQ1kf19AmZVK9ac9sHFpV6bxDaaYmZmZDB48mO7du/PJJ58YaliN0edxkS58ybrk0aNHnD9/Pn8mPHfuHDk5OXh4eODh4cG7775Lly5dcHZ2LvRe23Q5gSfvqu2zWj1XMqJ+RylLQ2pXG3vPETj2eKXMMhlEMbOzsxk+fDiurq588803Bo2p1BR9zJgl+5Lj+Orw9TL7kjUlMzOTixcvFjLJ8fHxdO7cGQ8PD/z9/fn6669p2rRpqf+fVAViD0XFFzn6qd1/ErX7Tyrx/ZK617tiKhQKAgICsLGxMUpMpaZkZGRQr1690huWkQ3ht1m8NxpZrnq3naoC28Gr8fx2PZG53u755QA1JScnh8uXL+cr4blz54iJiaF169Z4eHgwYMAA5s6di7u7u8YxAVN7N+f3mETNCsRaFj+mXhVTCMGkSZN49OgRu3fvxtLSaKdT5UaXx0V5ShlFVk7pWTEK+pKBMiunUqkkJiamkDmOjIykadOm+SZ50qRJtGvXDmtr3S0X2jd2ZK63e5l/PxXVrSyY6+1e7HONNKUsayQhBO+//z5Xrlzh0KFD2NjYaDKU0dDVcdGf9x6zeG+02v9pGVdPkLhrGQA1u/hQu99/Nz+zcpQs3htNu6cci9SsFEIQGxtbyBxfuHCBWrVq5SvhsGHD6Ny5s0FiWVVfnpIsggqJJG+mLM0ilEsxy7NG2rXuOw4fPsyJEyfM8jxQV2vM74/fUOsTzk1N5NGBQLCQglK9GZTlKgg8foPFg1wLmeNz586hUCjyd8jvv/8+Hh4eODk5aS2vpgR4NqXdU45aF4hVUWbFLM8a6ciVBygv3uD0wYPUqlWrrEOYFLpQzHxf8hN/LyEESXuWI61ZBxsnFzKjflf7vhCwPzKWX9/zpVPrZ/Dw8GDMmDF89913NGnSxOQ2ke2ecmRlQBeS0uWEXowlcNNOGjd7hhYuT+HeoCYjOpX91KFMilneNVIuFlh3HcXh2zICigY6mwW6OC4qzpecdm4nstirNBiznNRzO0vso1q1aizdcoLJvZprJYshqWNnzaSeT/Pzh6F8GPA5PXp0KHcfpSqmujVS6rmdpEceIifxLgglDt1H4+jlX+g9ea4odo1kDuhixlTnS85+eJvkEz/j6BVANedmpfaRrRBci0vXSg5jkZycrLHFLPXsRt0aKTvuBhY2dkhr1i3xXdUayRzRhWKmyopefc28dhoUucjuXiZhy8fI7vwJQFbMWZKPryumnxyt5DAWycnJGl+PKXHGLG6NVHdInjsxYesislITin1fCDh27SFJ6XKjeDS0QRfHRfY2av68QgAC2d8XCn2cmxKP/H50Mf0Y/uqytgghePTokcYzZomKWdwaqTxIgNCLsUzq+bTWfRkSXRwXude3x9oyrpA5d/TyL7TsSdz9FRl/HSlyXKTCxtIC9wbGub6sDZmZmUilUo2PCUs05cXF25UHWa6S6AdpWvVhaBQKBXK5XKsaQQAjOj+ltSwCGNFJ+34MjTZmHEqZMdWtkTTB3NZImZmZ2Nraan0cU9fOmu7NanH02kOQqJ8D6g6eTt3B09U+k0jyzv3MbRkEaGXGoZQZU+0aSQPMbY2kq8iiBw8eELFuIRZoZnVsLKVM6W0+x0QF0WZHDqUoZt4aqWiTtD8PkLj7K7LjbwKQGRNO4u6vyLx+pkhbc1wj6eSoKDqabt268coL3fnYtz3VrcoXvGJjmedLNsejNtDelJf41ypujSS/d5WMv46gSM1zTeYk3CLjryNkx/9dpK05rpG0VczTp0/Tu3dv5s+fz5w5c3j1uabM9W5JdStpiaFekGe+pSiwidrLy510U0jLGGhryku01cXF25W0LiqIua6RtDkq2rFjBxMnTmT9+vUMHPjfZf7y+JIn93yaBW+vYerUqaxatcrkXI9lQVtTXuoiUtt4O3NcI2l6VBQUFMTChQvZt2+f2jvyT/qSox+kkSrLwd7Gqogv+ZdffqFbt26sWLGCadOmaf07GRq97spB83g7a0uJ2a6RymvKhRD873//Y8uWLZw8eZJmzUp2Nap8ySVRs2ZNdu3axXPPPUfLli3p169fmeUxBR49eqRVpboyrcgDPMu3RrJEieTSdoa2KdllaaqURzFzcnIYN24chw8f5tSpU6UqZXlQVTnz9/cnJiZGZ/0aAr3uygsS4NmUzRM9eaGVM9aWFtg8sVu3sbTA2tKCF1o5s3VKD7zqQ0BAgFnWMizrcVF6ejpDhgwhKSmJo0eP6iUesnfv3nz88cf4+vqSkpKi8/71hcEUE/5bI52e9TzT+z+DQ/I12tQSvNShEdP7P8PpWc+zMqAL7RvX4vvvvyc5OZm5c+dqLJyxKMuMGR8fT+/evWncuDHbt2/X61XfyZMn07t3b/z9/VEoyr/WNwZ6PS4qDtUayenGXt7paM1XozowqefThXbf1apVY+vWrYSEhLBhwwaNBTQGpSlmTEwM3bp1Y8iQIaxatcogd5m++eYbMjIyzOaLrtfjotKQyWQlOunr1q3Lrl276NOnD82bN8fT01Ob4QxGenp6sd/2iIgIfH19WbhwoUEziVhZWbFlyxa6du1KmzZtCAgIMNjYmmBQU/4kcrm81Bt3rVu3Zs2aNQwfPpy7d9Vfjjc1ijsu2r17N4MHD2b16tVGSW+j+qJPnz7d5CqZFUSpVPL48WPTVkyAwYMHM336dHx9fcnIyNBmSIOgzpT/+OOPTJgwgbCwMAYPHmwkyaBNmzb89NNPDBs2jH/++cdocpREWloa1atX16oEjlaKWZopL8j7779Px44dGTNmjMnv1At6foQQfPzxxyxZsoTffvuNZ5991sjSgY+PD1OmTGHo0KFkZWUZW5wiaGvGwUAzJuTVzg4KCiI+Pp758+drM6zeUZny3NxcJk6cSFhYGKdPn6ZFixbGFi2f2bNn8/TTTzNhwgSTq56r7Y4cDKiYANbW1mzbto0NGzbw66+/ajO0XsnIyMDCwoKhQ4cSGxvL8ePHiySUMjYSiYSffvqJ6Oholi1bZmxxCqHtjhwMaMpV1KtXj507d/L222+b7AI+JSWF999/HycnJ3bt2mWyCRtsbW3ZsWMH33zzDbt37za2OPmYlSkvSLt27fIX8Pfv39dGBJ1z8+ZNoqKi8PLyYs2aNUapYVkennrqKbZu3crrr7/O1atXjS0OYGRTLoTQWDEhbwH/1ltv4evrW6jCljE5f/48Xl5e1KhRg7lz55pNuJmnpyfLli3Dx8eHR48eGVsc486YqhqL2pS0mzVrFq1atWLs2LFG36nv37+fQYMGERgYCGB22YRfe+01hg4dyssvv0xOjnHvWBl1janNbKlCIpGwatUq7t27x8KFC7XqSxt+/vlnxo4dy86dOxk6dKjZVqxYunQpVlZWRk8jrgtTjtCQhw8fitq1a2v6eiEePHggmjRpIkJCQnTSX1lRKpVi8eLFomnTpiIqKkoIIYRcLheWlpZCqVQaVBZdkZycLNzc3MSqVauMJsPIkSNFcHCwVn1o7CvXZEdeHPXr12fnzp3079+fZs2aGaRCmkKhYNq0aZw5c4bTp0/nF1VVeX3MZX35JI6OjuzatQsvLy/c3d3x8vIyuAxmb8oL0qFDB3744QeGDh2qd1dbVlYWI0aMICYmhhMnThSq9FsRqlU888wz/PLLL7z88stGKdJq1M2PrhUTYNiwYUyePFmvrrakpCT69etHjRo12LNnD/b29oWem+v68kkGDBjArFmz8PHxIT3dsNnijHpcpEtTXpA5c+bQvHlzXn/9dZ272m7fvk337t3p0aMH69evp1q1akXaVKSKaO+88w5dunThtddeM+ipR4Uy5SpUrrabN2+yePFinfV76dIlevTowdSpU1m6dGmx1TMqgilXIZFICAwMJC4uzmC1lRQKBWlpaTg4lK00X7Foums6duyY6Nmzp1Y7r5L4559/ROPGjcXWrVu17uvQoUPCyclJbNmypdg2D9NkIuj4DTHiy92i1ZvfiXeCL4qg4zdEYppM6/GNTVxcnGjSpEmJv7+uSEpKEo6Ojlr3YxK7cnU0aNCA7du3M3DgQFxdXenYsaNG/WzcuJH33nuP0NBQtaWnixY8ABxc2XHpH4MVhdI3zs7O7NixgwEDBtC8eXM6dOigt7F0YcbBBE15QTp37kxgYCBDhw4lLi6uXO8KIfj888+ZM2cOR48eVauUG8Jv47c6nENR8chzlUVSLsr+/ezg1Xj8VoezIfy2Nr+OUenYsSOBgYH4+voSHx+vt3F0sSMHLe78yOVyg9TuGTlyJFevXmXo0KEcP368TGMqFAree+89jh49yqlTp3jqqaK5kwxRFMrUGDlyJJcvX2b48OEcPXpU7eZPW3Ti9UHLXbm+Z0wV8+bNw8XFpUxBsTKZDD8/PyIjI/n999/VKqW6ggfZ8X8Tv/kj7n09mrtfDOef1W+SdnFPofdURaEiYx/r5PcyBgsWLKBevXpMmTJFLwHGupoxTdqUq5BIJKxdu5aoqCiWLl1abLvk5GQGDBiAhYUF+/fvx9HRUW07dQUPErYuQnbrDyxr1cfWrRs5SbE8OhiE7E5koXbmXPAAwMLCgvXr1xMREcF3332n8/51tcY0eVOuwtbWlp07d/Lss8/SsmVLfH19Cz2/d+8eAwcO5IUXXuCLL74o9jhIXcEDochFkZYIQB3vd6jm1JScpHtkx90gN6XwesycCx6osLOzK5QXqX///jrru1KZchWNGjVi+/btjB8/nj///DP/88uXL9OtWzfeeOMNli9fXmKFX3UFDyRSS2p2GQJA0t5vSAz7kuy4m1jVc8X2meeKtiev4IE507RpUzZv3kxAQIBO8yJVKlNeEA8PD7777jt8fX1JSEjg+PHj9O3bl2XLlvHee++V+n5xBQ9sWzyH1MGZ7AcxZFw5BhZSbFt4IqlWtECAORY8UEfPnj1ZuHAhPj4+OsuLVOlMeUH8/Py4cuUKPXv2JCkpiZCQEPr06VOmd9UVPFBkpZKwZT4iR46z/1KsnFxI2PwRKad+RVrDkZqdXizyzu1/4omNjaVBgwZaBUsbm4kTJ3L58mVeeeUVdu3alf+7lKXCsjp0Zcq1OmCvU6eO1gJoiqOjI3fv3qV///707t27zO+pK3iQ+zgekSMHC0usGzyDxNIKqzqNyX4QQ07iPbX9REf+Qddl40hKSqJx48a4urrStGnTIv8aNGhQ4tLCFFi+fDkDBw5k9uzZ+E+bU+YKy+ocDiZxjmkMU65UKpk5cyb79u3j4sWLvPLKK3z55ZfMmDGjTO+rKwplVacxFjY1UcrSiA+ei6VjfTKu/gaAdeOiyUdtLC14d9xIJq39EJlMxp07d7h9+3b+v927d+f/nJycTJMmTdQqraurK87OzkZXXCsrK0JCQugy+j22B50kF0mpFZZ/u56otuZ4pTTlcrmcsWPHEhsby8mTJ6lduzY7d+7E09MTd3f3MqVuGdH5Kb46fL3QZxbVbKj38gIe//YL2XE38zY+tRpg12EgNVoW9RgVLHhgY2ODm5sbbm5uasfLysoqori7du3i1q1b3L59m9TUVLWKq5qBnZ2dDRK0vC8mjWpdRyFXlH62WZLDwSRMuSFnzJSUFF566SVq1arFoUOH8r8UjRs3ZuvWrfj4+HD06FHatGlTYj/FFTywbuiGs9+iUuUob8GD6tWr4+7ujru7u9rnmZmZRRR3+/bt+T+npaXh4uKiVmmbNm1KvXr1tFZclcOhoFIm7l6O7PYlFFmpWFSzpVr95tTq9RrV6v+XolvlcChYYblSmfL79+8zaNAgevbsyTfffFNks+Hp6clXX32Fj48PZ8+eLTWzrykVPLC1taVly5a0bNlS7fOMjIxCinvr1i0uXLiQ/98ZGRn5iqtunevk5FSq4qpzOOSmJGDdpC0W1rbI7kQiu3WRhKR7PDVlbaF2KofDyoAu5OTkkJWVRc2a2td1MnlTfvXqVQYNGsSUKVP44IMPiv0j+/v7c+XKFYYPH87hw4dL9ANrWvCgupXhi0LVqFGDVq1aFZtoPz09nTt37uQvDW7fvk1ERET+z1lZWbi4uBS7OcOmptoKy/X9P8v/WR53g7h176JIS0IocpFI/1Obgg4HRWYKjo6OOll6mLQpP3nyJMOHD+eLL77g1VdfLbX9okWLGDZsGFOmTGH16tUl/oFU66LFe6OR5SrULvZVSCR5M6W6xb6xsbOzo3Xr1rRu3Vrt87S0tELLhNu3bxMeHp7/s0XrAdR4dhRYFs04knohjJzEe/k11e27Di2klCpUDofezrk6WV+CCZvybdu2MXnyZDZu3Fhml5mFhQUbNmyge/fufP3110yfXnKRrCeLQgmhJLuARStYFGpK7+ZmWRqmZs2atG3blrZt26p9PvWXCPZcfaj2WWb0KeT3/gJAWrMu1o3Uz9oqh0P7ajKdrC/BRE35ihUrWLJkCQcOHCh3gHBBP7C7uzuDBg0qsX3BolCfhRxn3+k/edarj9qiUBWRLGXxVqW+/2eI3Gyy/r7Iw+2f8nDHEhpNWo2lQ70ibVNlOTo7KgITM+VCCObMmcO2bds4efIkrq6uGvXj4uJCaGhofgxnWQoh1bGz5jnHDG4+Cuen1z7QaFxzRJ3DQZkjRyK1RGIhRWJZjerNOiOpZoOQZ5L7OE6tYtrbWOnsqAhMyJRnZ2czfvx4YmJiOHXqFHXrale8qlu3bvmJps6ePVsmL9Xjx4+LDZWrqKhzOGT/c43EsC+wbtwaCxs75PeuIOSZWNg6UM25aEU3VYXl5EjdHBWBlkEcujLlaWlpDB48mJSUFI4cOaK1Uqp47bXXGDZsGCNGjCA7O7vU9pVRMdVVWJbWrINlrYbIbl0i/c9DKGXp2Lr3wHn0Yixsit4gVTkcKpQpj4uLw9vbm65du7JixQqd18xZsmQJQ4cOZdq0aaxcubLEnXplVMy6dta0rg0X4pRI/nWNWtVuVOi4qCQKOhySk5Np3LixTuQyatjbtWvX6NatG8OGDSMoKEgvhZykUimbNm3i9OnTrFixosS2ycnJlUoxhRB8++23nPnpY6wtNVOFgg4HXXl9QMsZUxtTfubMGV566SWWLFnCuHHjNO6nLKgq2Xbr1g03NzcGDBigtl1lmjFlMhlvvvkmFy9e5HTYDk7FS7R2OOjSlBtlxty1axe+vr6sXbtW70qpwtXVlZCQEAICAoiOjlbbRtuiSebC/fv36dWrFxkZGZw+fRpXV9dyV1iubiVlrndLvQRwgIaKKbRIc/3DDz8wefJk9uzZU+oZo67x8vJiyZIlxaaErgwz5pkzZ+jatSu+vr5s3ry5UDqc8lRY3jzRs4gXTJemXKMUMTKZTFhZWZXrHaVSKT766CPRvHlzcePGDU2G1RnTp08Xffv2FdnZ2YU+b9OmjYiMjDSSVPrnxx9/FE5OTmL37t2ltk1Mk4mVJ26Id4P/EK+vixDvBv8hVp4oOWVOw4YNxb1793Qiq0aKmZKSIuzs7MrcPjs7W4wbN054eHiI+Ph4TYbUKbm5uWLQoEFiypQphT5v1KiRuHv3rpGk0h/Z2dliypQpws3NTURHR+ttHBsbG5GRkaGTvjQy5eUx4+np6flpSY4dO0a9ekW9BoZGKpXy66+/cuzYsfxiAFAxTXlCQgL9+vXj7t27nD17ttiAZm2RyWQolUqqVy96eU8TNFLMsu7IExIS6NOnDw0aNGDnzp0mld7PwcGBsLAwPvnkE44cOUJOTg4ymazC5MYEuHjxIh4eHnh5ebFz507tUwOWgGp9qbNo+/JMr6pUfa+vPiFcxnxWYqq+mJgY8fTTT4t58+aZdKL9Y8eOiXr16onw8HBRp04dY4ujMzZt2iTq1q1rkNSDQgjx119/CXd3d531V6ZzzKKp+pTQsE2xqfpUxeY/+eQTJkyYoJtvkJ7o3bs3CxcuZPTo0UXSXpsjCoWC2bNnExoaypEjR2jXrp1BxtXlURGU4YA9Lyta8cG0T96c82miYM3ssaxZs4YhQ4boTFB9MnHiRI4ePcq+ffvIzc3ViwfKECQnJ+Pn54dCoeDcuXMGvV6t06MiSllj/peqr+QIb/jv5lxwtJy3vw0xG6VUMXbsWCwtLY1evElTrly5goeHB61bt2b//v0Gv/OvS68PlKKYT6bqAxC52Tw6uJJ73/pz94thxP0yE/k/1/KfS6ys2RQlN7tUfWlpafTo0YMDBw6watUqY4tTLnbs2EHv3r2ZN28ey5cvN8qMr2tTXqJiPnlzDuDR4VWkXdyNtIYj1Vt4Ir8fTXzw/1BkphR6z9xS9T1+/BgnJyfCwsL46KOPOHbsmLFFKhWlUsmCBQt4++232bt3L2PGjDGaLAY15U+ab0XGY9IjD4PEAme/xTj5fkCN1r0R2VmkXdhd6D3VzTlzQeUnb9GiBZs2bWL06NHcvHnT2GIVS1paWv6N0IiICDw8PIwqj0FN+ZPkJN4FZS5SeyekNRwBqFY/L+QpO+FWobbmlqqv4OF63759mTdvHkOGDNFZFjRdcuPGDTw9PalXrx5Hjx6lfv36xhbJsKb8SRQZyXkvVfvvcF3y78+qZyrMLVXfk16fKVOm0KdPH0aPHo1CUf7ECPriwIEDdO/enWnTpvHDDz/oJY+6JhjUlD+JtEbewMpsWf5n4t+fVc8Kkiozbt3s8qAuSPjrr78mOzubmTNnGkeoAgghWLZsGePGjSM0NJTJkycbW6RC6Foxy7V9s6rbGCwsUaQ+RJGRjLRGLeQP8hJUVatX9EajvU3RS/Smijo/uZWVFVu2bOHZZ5+ldevWvPHGG0aRLTMzk/Hjx3P9+nXOnj2rs+sLuuTRo0fGM+XSGrWwa9sXhJL4X+fycOdSMq/+hqRadWp2LpxpTXVzzlwoLoCjVq1a7Nq1i9mzZ/Pbb78ZXK47d+7Qo0cPpFIpv//+u0kqJRjZlAPU6jcRu04vosh4TOb1cKwbueE86hOktoUDBAqm6jMHSoped3d3Z8OGDYwaNYpbt26pbaMPTpw4gaenJ/7+/qxfv15nkTu6RghhWFMukRQ9MrKwsqbOgDepM+DNEt8rT6o+U6C0kLcBAwYwZ84chgwZwunTp/XqVxdCEBgYyCeffMKGDRt0WlVCH2RkZGBlZaXTPAMlKqaNpdQkUvUZgrLEYr711lv89ddf+Pv7s2PHDr3kXpfL5UydOpWzZ89y+vRpnn66aIIBU0PXsyWUYsrnertT3ap81t4Yqfq0RS6Xk5ubW6qplEgkrFixgvT0dGbPnq1zOR48eECfPn1ITk7mzJkzZqGUYATFLNfNOUDkypnep6nJpeorDdVsWZYgVysrK0JDQ9m2bRvr1q3TmQxnz57Fw8ODQYMGsWXLFrMKWNa11wfKsPkp88251s54yc9z4sfS00WbGuW9UlGnTh3CwsL44IMPOHXqlNbjr1u3jiFDhhAYGMhHH31k9GIB5UXXXh8o4zlmwVR9oRdjiX6QRqosp0iqvsxhrejcuTObNm3ilVde0amg+kST++QtW7bk559/ZsSIEYSHh+Pi4gKUrz5OTk4OM2bMYN++fZw4caLYdNemjj5MebkO2OvYWTOpZ/HrHltbWzZu3MjAgQPp0aMHTZo00VpAQ6DpJbRBgwbxwQcf4OPjw8ot+1h79p8y18dJTEzk5ZdfxsbGhoiICLO+BGcUU15eOnXqxHvvvceYMWNMysdcEtrcjnz33Xep7zWSV36K4FBUPPJcZZGSgLJ/Pzt4NR6/1eEsCT2Jh4cHzz77LGFhYWatlKAfU66XxczMmTNRKpUsX75cH93rHG2SaW08e4c7tTsjLKzKHOW/MjwB3xlfsGTJErMu96fC6Ka8rEilUtavX4+Hhwf9+vUrd7pqQ6PpjKmqjyMrEOWftPdbZPevokhNRCK1olrDZ6jVZxzVnJrmt5FYWXMgXkpk7GOzOlYrDoMfF2lD06ZN+eqrr/D39ycrK0tfw+gETRVTXX2c9MiDWFjXoEarnkisbZH9fYGEkPmI3MKJY80xyr84dB3AAXpUTMirvdOuXTtmzZqlz2G0RpNdeWK6XH19nLFf02DMl9QZ9Db1R38KgCItiezEu4XamWOUf3GY1YwJeZ6SoKAgduzYwf79+/U5lFZoMmOGXlAfnW9d/z9XrFD+W4JaYoHUruiMYm5R/sVhdooJeWFj69at44033iAxMVHfw2mEJpuf6LjUIrvvgiizs0ja8zWQV7jJUo1imluUf3GYnSlX8fzzz/PKK68wYcIERGlbVyOgyYyZKsst9pkiM4X4TXOQ34/Crv0LOPYuPjmtOUX5q0OpVJKSkqLzIy+D+b4WLVrE33//zdq1a0tvbGA0UUx19XEgrzho3IYPyI6Lwf65kdQZNK1EH7w5RfmrIy0tDVtbW53fZTfYzXhra2s2btxInz596NWrl0lFzmiimOrq4wDE/TIDRfojpPZOiBw5jw7nJU+o0aoX1g0LpwCUoqSR6STA0wh9mHEw4IwJ0KZNG/73v/8REBBAbm7xptCQCCE0Ukx19XEAFOl5KbQVqQ9JO78r/19O4j21Y386wYdRo0Zx/Phxk1zmlIY+Nj5gwBlTxbRp09izZw+ffvop8+bNM/TwRZDJZFhYWJS7AkddO2t6PePEoaj4QkdGLh/uLv6lAkgkMKB1Q5ZGX2b9+vVMmTIFgMmTJzNmzBizcVPqSzENHl9lYWHBunXr+P777zl79qyhhy+CNu7Iqb2bY2OpmUtRFeXv4ODAtGnTuHLlCkFBQflVJMaPH8+FCxc06tuQ6MNPDkZQTICGDRvy/fffExAQQHp6ujFEyEebAI72jR11FuUvkUjo1asXwcHBREdH06xZM4YPH07Xrl1Zu3YtmZmZGsmob/QRWQRGUkyAESNG0KNHj1JriusbbfOu66I+zpM4OzszZ84cbt68yfz58wkNDaVJkyZMnz6da9euFfueMagwprwg33zzDUeOHGHHjh1Gk0EXBQG0rY9THFKplBdffJE9e/Zw7tw5bGxs6NmzJ3379iU0NJScHOOfgepLMSXCyFvBU6dOMXz4cP744w8aNGhg8PE3bdpEWFgYv/76q076Ky3KX1vkcjnbt28nKCiImJgYxo8fz4QJE4yWCGHixIl07tyZSZMm6bRfo+d07t69OxMmTOD1119n7969uqt6UEZ0XaavtCh/bbG2tsbPzw8/Pz+uXLnCypUrad++PV5eXrz55psMGDDAoHeGKqQpVzFv3jySkpIK1dwxFOZccbd169Z899133L17l8GDBzNnzhxatGjBsmXLDBaXUKEV08rKig0bNrBgwQKioqIMOnZFKDplZ2fHhAkTuHDhAps2beLKlSs0b96cgIAATp06pdeD+wrh+SmJZ555hsWLF+Pv7092dnbpL+iIiqCYKiQSCc8++yzr1q3j77//plOnTowbN4727dsTFBREWpruI5kq9IypYsKECTz11FPMnz/fYGNWJMUsSO3atXnvvfeIjo5m+fLlHD58GBcXF958800iIyO16jsxXc7KEzd5d/MfZHu+zhenHrLyxE2dBj0bfVf+JAkJCXTo0IHg4GB69uyp9/H69+/PzJkzGTBggN7HMjb379/nxx9/ZPXq1flKOmLEiDK7Y9UWIvsXG0sLBBS6oqwNJqeYAHv27GHq1Kn8+eefeq1/CODh4UFgYKDRk+sbktzcXMLCwggKCuLSpUuMHTuWSZMmlRjxVVohMhUSSZ67da63u1apgkzKlKt48cUX8fb25q233tL7WOa8K9cUS0tLXnrpJQ4ePMipU6dQKpV4enoycOBAdu7cWSTyS5NCZIv3RrEh/LbGMprkjAl56Z07derEggUL8PPz09s4devWJSoqCicnJ72NYQ5kZWWxZcsWgoKCiI2NZeLEiYwfP56E3Or4rQ4vlI5SdieS+F/nqO2njve72LXrB+S5XzdP9NToirLJKibA+fPn8fb25vz583pJNyOEwMrKiszMTJOp/mAKXLp0iaCgIEJCQnAJWEyKnQsFlSQn+Z/CdZ2yZaRHHgTA2X8pNo1bA3lm/YVWzqwM6FJuGUxaMQE+/fRTDh06xJEjR3Tu0UhPT8fZ2ZmMjAyd9ltRuPUgkX7fhqOgZG9c6vkwkg//QDXnp2kw7ptCz6wtLTg96/lyu2NNco1ZkFmzZpGTk6OXdDMV9ahIVxy4noJlKfGmQgjSLuwCoKaHb5Hnml5RNnnFlEql/PLLLyxdupQ///xTp33r2k9e0SjtijJA1o0IcpMfILWrTY2WXkWea3pF2eQVE8DV1ZXly5frPN1MZdyRl4eSriirSDu/EwC7joOQSNXf+NTkirJZKCZAQEAArVu31mnu8ypTXjLFXVFWkZ1wG9mdSCSW1ajZ0buEfsp/RdlsFFOVbmbr1q0cPHhQJ31WKaZ6srKy2Lp1K+cP70LkFu9mTP13tqzRqneROk8qNC1EZjaKCXn+33Xr1vH666+TlJSkdX9Vivkf2dnZ7Nmzh1dffZWGDRsSFBTEyM6NsbZW765UZKaQefUEADU9fIrtV9NCZEYPFC4vffv2ZdSoUUycOJHQ0FCtAosru2IqFAqOHz9OcHAw27dvx93dHT8/P5YtW5ZfavrKL+eLXFEGkNo60GTGthL716YQmdkpJsDixYvp2rUrP//8M2PHjtW4n+TkZBo1aqQ7wcwApVLJmTNnCA4OZsuWLTRu3JhRo0Zx8eJFtU6Mqb2b83tMosELkZmlYtrY2LBx40aef/55vLy8NE438/jxY1q3bq1j6UwPIQQXLlwgODiYkJAQHBwc8PPz4+TJkzRvXrLiqK4o5/nKSz46Koi2hcjMUjEB2rZty5w5c3j11Vf57bffNErqVNFN+V9//UVwcDDBwcFIJBL8/PzYu3cvbdq0KVc/qiihSh9dVFbeeecdbG1tWbJkiUbvV0TFjImJYdGiRbRp0wZvb2/kcjmbN2/m+vXrLFy4sNxKqUJfV5SLw+R95aURGxtLp06d2L17N127di3Xu506dWL16tV07txZT9IZhrt377J582Y2b95MbGwsL7/8Mn5+fnh6eurlxqS+rygDICoAISEhokWLFiItLa1c77m6uoobN27oSSr98uDBA/Htt9+Kbt26iTp16ogJEyaII0eOiNzcXGOLphPMfsZU8dprr2FjY8MPP/xQ5ndq1arFzZs39XLLTx8kJSWxbds2goODuXjxIkOGDMHPz49+/fpVvLA9Y38zdEVKSopwdXUVO3fuLFN7hUIhLCwsRE5Ojp4l046UlBTx888/C29vb2Fvby9efvllsXXrVpGZmWls0fRKhVFMIYT4/fffRf369cWDBw9Kbfv48WNRs2ZNA0hVfjIyMsTmzZvFSy+9JOzt7YWPj4/YtGlTuZcq5kyFUkwhhJg7d67w9vYWSqWyxHa3b98WjRs3NpBUpSOTycTOnTvF6NGjhYODgxgwYIBYs2aNePTokbFFMwoVTjGzs7NFly5dRGBgYIntLl26JNq2bWsgqdSTnZ0t9u/fL8aNGydq1aolevXqJQIDA0V8fLxR5TIFzPaAvThU6WZ69OhBnz59cHd3V9vOWGeYSqWS33//neDgYLZu3UqzZs3w8/Nj4cKFlc49WhIVTjEB3NzcWLhwIf7+/pw5c0btjlVfqU3UIYQgIiIi3yXo5OSEn58f4eHhNGvWzCAymBtm7fkpiUmTJtGgQQMWLFig9rm+Z0whBJcuXWL27Nk0a9aM1157DQcHBw4fPsylS5f48MMPq5SyBCrMOaY64uPj6dChAyEhIXh55d1HSUyXE3ohlh3HIkjOkPFclw6417dnZGfdeC2io6Pz/dNyuTw/l2W7du0MnvvTnKnQigkQFhbGtGnT2Lj/JD+fi9NL3p1bt26xefNmgoODefjwYb5LsGvXrlXKqCEVXjEBvN9eQnT1Vgippc4iY+7fv8+WLVsIDg7m77//Zvjw4fj5+dGjRw+kUs1KrFTxHxVy81OQDeG3+duxA8ocJZQj7w5QRDkfPnxIaGgomzdvJjIykqFDh/LJJ5/w/PPP67yWYmWnQs+Yf957XCTvTtzGD5Hf+6tQO6u6TWg4vnCabVXenSZ2sH37doKDgzl79ize3t74+fnxwgsvYG2to0iaKopQob/m3x+/gSxX/ZWAml3+u0Clrsi9LCeXgCUbuLNhLn379uWNN95g27Zt1Khh5lVJzYQKq5iJ6XJOXH9Y7Jqydr+JJb4vkJDp0JRL0TdxbVBXDxJWURIVVjFDL5ScL+feV6MQgHX9p3HsPRbrBs8UaWMplXIwJoVJVYppcCrsAXtxeXcsqlWn+tMe2Lb0wtLeCdmdSBI2z0ORnlykraZ5d6rQngo7YxaXd8dpxLz8s0WhyOH+D5NQpCYguxtJjVa91PRj/LJ4lZEKO2Oqy7ujzJHlF7ovQjEH4Zrk3alCeyrsjOle3x5ry7hC5lyZkcL91ZOwcWmPpb0T8vvRKFITsKjhiI1L+yJ9aJp3pwrtqbAz5ojORfPlWFSviV2b58l9dJ+Mv46iyHxM9RaeOPstVpsUStO8O1VoT4WdMevaWdPrGadCeXcsrG2pM+jtMr2vTd6dKrSnws6YkJd3x6aUVM3FoU3enSq0p0IrpirvTnWr8v2a2ubdqUJ7KqwpV2GMvDtVaE+FDuIoSGTsYwKP3+DYtYdIyDs8V6GKx+zj5sSU3s2rZkoToNIopgqD5N2pQmsqnWJWYR5U6M1PFeZLlWJWYZJUKWYVJkmVYlZhklQpZhUmSZViVmGS/B8TvidIYEQYPwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "G = nx.petersen_graph()\n",
    "plt.subplot(121)\n",
    "#matplotlib.axes._subplots.AxesSubplot object at ...\n",
    "nx.draw(G, with_labels=True, font_weight='bold')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
